package com.lfg.leetcode.leetcode0;

/**
 *
 */
public class No10RegMatch {

    public static boolean isMatch(String str, String pattern) {
        if (null == str || null == pattern || "".equals(str) || "".equals(pattern)) {
            return false;
        }
        int sl = str.length() - 1;
        int pi = pattern.length() - 1;
        return isMatch(str, pattern, sl, pi);
    }

    private static boolean isMatch(String str, String pattern, int si, int pi) {
        if (si < 0) {
            return true;
        }
        if (pi < 0) {
            return false;
        }

        if (pattern.charAt(pi) == '*') {
            if (si <= 0) {
                return isMatch(str, pattern, si, pi - 1);
            }
            if (pi - 1 >= 0 && equals(str, pattern, si, pi - 1)) {
                return isMatch(str, pattern, --si, pi) || isMatch(str, pattern, si, pi - 2);
            }
            return isMatch(str, pattern, si, pi - 2);
        }

        if (equals(str, pattern, si, pi)) {
            return isMatch(str, pattern, --si, --pi);
        }
        return false;
    }

    public static boolean equals(String str, String pattern, int si, int pi) {
        if (pattern.charAt(pi) == '.') {
            return true;
        }
        if (str.charAt(si) == pattern.charAt(pi)) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
//        System.out.println("aa" + isMatch("aa", "a"));
//        System.out.println("aab=" + isMatch("aab", "c*a*b"));
//        System.out.println("caab=" + isMatch("caab", "c*a*ba"));
//        System.out.println("ab=" + isMatch("ab", ".*"));
//        System.out.println("ab=" + isMatch("ab", ".*"));
        System.out.println("aa" + isMatch("aa", "a*"));
//        System.out.println("aaa=" + isMatch("aaa", "a*a"));
//        System.out.println("mississippi=" + isMatch("mississippi", "mis*is*ip*."));
//        System.out.println("mississippi=" + isMatch("mississippi", "mis*is*p*."));
//        System.out.println("aaba=" + isMatch("aaba", "ab*a*c*a"));
//        System.out.println("aaa=" + isMatch("aaa", "a"));


    }


}
